import java.util.*;

/**
 * 滑动窗口最大值
 * --->
 * 单调队列
 */
class SlidingWindows {

    public Deque<Integer> queue = new LinkedList<>();


    void push(int nums[],int index) {
        while (!queue.isEmpty() &&nums[ queue.peekFirst()] < nums[index]) {
            queue.pollFirst();
        }
        queue.offerFirst(index);
    }

    void pop(int nums[],int index) {
        while (!queue.isEmpty() && queue.peekLast() == index) {
            queue.pollLast();
        }
    }

    int max(int nums[]) {
        return nums[queue.peekLast()];
    }


    public ArrayList<Integer> result = new ArrayList<>();

    public int[] maxSlidingWindow(int[] nums, int k) {

        queue.clear();
        result.clear();

        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (i < k - 1) {
                push(nums,i);
            } else {
                push(nums,i);
                result.add(max(nums));
                pop(nums,i - k + 1);
            }
        }

        return result.stream().mapToInt(Integer::intValue).toArray();
    }

    public static void main(String[] args) {
        System.out.println("Hello and welcome!");
        SlidingWindows s = new SlidingWindows();

//        System.out.println(Arrays.toString(s.maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
        System.out.println(Arrays.toString(s.maxSlidingWindow(new int[]{-7, -8, 7, 5, 7, 1, 6, 0}, 4)));
    }
}
